|
Johnson's algorithm is a way to find the shortest paths between all pairs of vertices in a sparse, edge weighted, directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist. It works by using the Bellman–Ford algorithm to compute a transformation of the input graph that removes all negative weights, allowing Dijkstra's algorithm to be used on the transformed graph.〔. Section 25.3, "Johnson's algorithm for sparse graphs", pp. 636–640.〕〔.〕 It is named after Donald B. Johnson, who first published the technique in 1977.〔.〕 A similar reweighting technique is also used in Suurballe's algorithm for finding two disjoint paths of minimum total length between the same two vertices in a graph with non-negative edge weights.〔.〕 ==Algorithm description== Johnson's algorithm consists of the following steps:〔〔 #First, a new node is added to the graph, connected by zero-weight edges to each of the other nodes. #Second, the Bellman–Ford algorithm is used, starting from the new vertex , to find for each vertex the minimum weight of a path from to . If this step detects a negative cycle, the algorithm is terminated. #Next the edges of the original graph are reweighted using the values computed by the Bellman–Ford algorithm: an edge from to , having length , is given the new length . #Finally, is removed, and Dijkstra's algorithm is used to find the shortest paths from each node to every other vertex in the reweighted graph. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Johnson's algorithm」の詳細全文を読む スポンサード リンク
|